package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC900 {
    public long startExecuteTime = System.currentTimeMillis();


    class RLEIterator {
        long curCounter = 0, sumCount = 0;
        TreeMap<Long, Integer> order = new TreeMap<>();

        public RLEIterator(int[] encoding) {
            for (int i = 0; i < encoding.length - 1; i += 2) {
                if (encoding[i] == 0) continue;
                sumCount += encoding[i];
                order.put(sumCount, encoding[i + 1]);
            }
        }

        public int next(int n) {
            curCounter += n;
            if (curCounter > sumCount) return -1;
            Long nearCnt = order.ceilingKey(curCounter);
            return order.get(nearCnt);
        }
    }

    public void run() {
//        输入：["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],[2],[1],[1],[2]]
//        输出：[null,8,8,5,-1]

//        RLEIterator solution = new RLEIterator(new int[]{3, 8, 0, 9, 2, 5});
//        System.out.println(solution.next(2));
//        System.out.println(solution.next(1));
//        System.out.println(solution.next(1));
//        System.out.println(solution.next(2));

        RLEIterator solution = new RLEIterator(new int[]{923381016, 843, 898173122, 924, 540599925, 391, 705283400, 275, 811628709, 850, 895038968, 590, 949764874, 580, 450563107, 660, 996257840, 917, 793325084, 82});
        System.out.println(solution.next(612783106));
        System.out.println(solution.next(486444202));
        System.out.println(solution.next(630147341));
        System.out.println(solution.next(845077576));
        System.out.println(solution.next(243035623));
        System.out.println(solution.next(731489221));
        System.out.println(solution.next(117134294));
        System.out.println(solution.next(220460537));
        System.out.println(solution.next(794582972));
        System.out.println(solution.next(332536150));
        System.out.println(solution.next(815913097));
        System.out.println(solution.next(100607521));
        System.out.println(solution.next(146358489));
        System.out.println(solution.next(697670641));
        System.out.println(solution.next(45234068));
        System.out.println(solution.next(573866037));
        System.out.println(solution.next(519323635));
        System.out.println(solution.next(27431940));
        System.out.println(solution.next(16279485));
        System.out.println(solution.next(203970));
    }

    public static void main(String[] args) throws Exception {
        LC900 an = new LC900();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
